package com.eddie.sort;

import java.math.BigDecimal;
import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        long start = System.currentTimeMillis();
        insertSort(arr);
        long end = System.currentTimeMillis();
        System.out.printf("花费时间是：%d毫秒\n", end - start);
        System.out.println(Arrays.toString(arr));

    }

    public static void sortColors(int[] nums) {
        int indexVal;
        int index;
        for (int i = 0; i < nums.length - 1; i++) {
            indexVal = nums[i + 1];
            index = i;
            while (index >= 0 && nums[index] > indexVal) {
                nums[index + 1] = nums[index];
                index--;
            }
            if (index + 1 != i) {
                nums[index + 1] = indexVal;
            }
        }
    }

    //插入排序
    public static void insertSort(int[] arr) {
        //第一轮 {101, 34, 119, 1} => {34,101,119,1}
        //定义待插入的数
        int insertVal;
        int insertIndex;//及array[1]的前面数的下标
        for (int i = 0; i < arr.length - 1; i++) {
            //将要插入的数字设置为当前下标+1的数
            insertVal = arr[i + 1];
            //将插入的默认索引设置为i表示已插入数组的长度
            insertIndex = i;
            //给insertVal找到插入的位置
            //1、insertIndex >= 0保证找插入位置时不越界
            //如果插入索引大于=0 并且 插入的数据小于插入下标的数据就表示还没找到插入的位置那么就将插入下标的数据后移一位;并且将插入的下标-1
            while (insertIndex >= 0 && insertVal <= arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //循环结束时说明插入的位置找到此时加一就是插入的位置
            //如果+1等于i表示找到的插入位置就是该数据则不用添加
            if (insertIndex + 1 != i)
                arr[insertIndex + 1] = insertVal;
        }
        System.out.println(Arrays.toString(arr));
    }
}
